#include <iostream>
#include "binary_trees.h"
#include <queue>

using namespace std;

int main()
{
  /*build a tree, like
   *             8(root)
   *              /\
   *             /  \
   *            /    \
   *           /      \
   *          3(2)    10(3)
   *         /   \      \
   *        /     \      \
   *      1(4)    6(5)  14(6)
   *              /  \    /
   *           4(7) 7(8) 13(9)
   */


  node *root = newNode(8);
  node *node_2 = newNode(3);
  node *node_3 = newNode(10);
  node *node_4 = newNode(1);
  node *node_5 = newNode(6);
  node *node_6 = newNode(14);
  node *node_7 = newNode(4);
  node *node_8 = newNode(7);
  node *node_9 = newNode(13);

  //add node_2, node_3 to root
  root->left = node_2;
  root->right = node_3;

  //add node_4, node_5 to node_2
  node_2->left = node_4;
  node_2->right = node_5;

  //add node_6 to node_3
  node_3->right = node_6;

  //add node_7, node_8 to node_5
  node_5->left = node_7;
  node_5->right = node_8;

  //add node_9 to node_5
  node_6->left = node_9;

  //lookup number
  cout << "should be true" << endl;
    //lookup 8
  cout << "8 is in the tree: " << lookup(root, 8) << endl;
    //lookup 3
  cout << "3 is in the tree: " << lookup(root, 3) << endl;
    //lookup 10
  cout << "10 is in the tree: " << lookup(root, 10) << endl;
    //lookup 1 
  cout << "1 is in the tree: " << lookup(root, 1) << endl;
    //lookup 6
  cout << "6 is in the tree: " << lookup(root, 6) << endl;
    //lookup 14
  cout << "14 is in the tree: " << lookup(root, 14) << endl;
    //lookup 4 
  cout << "4 is in the tree: " << lookup(root, 4) << endl;
    //lookup 7
  cout << "7 is in the tree: " << lookup(root, 7) << endl;
    //lookup 13
  cout << "13 is in the tree: " << lookup(root, 13) << endl;

  cout << "should be false" << endl;
    //lookup 0 
  cout << "0 is in the tree: " << lookup(root, 0) << endl;
    //lookup 2
  cout << "2 is in the tree: " << lookup(root, 2) << endl;
    //lookup 5
  cout << "5 is in the tree: " << lookup(root, 5) << endl;
    //lookup 9 
  cout << "9 is in the tree: " << lookup(root, 9) << endl;
    //lookup 11
  cout << "11 is in the tree: " << lookup(root, 11) << endl;
    //lookup 12
  cout << "12 is in the tree: " << lookup(root, 12) << endl;
    //lookup 15
  cout << "15 is in the tree: " << lookup(root, 15) << endl;
    //lookup 100
  cout << "100 is in the tree: " << lookup(root, 100) << endl;

  //printPreOrder
  cout << "print pre-order" << endl;
  printPreOrder(root);
  cout << endl;

  //printInOrder
  cout << "print in-order" << endl;
  printInOrder(root);
  cout << endl;

  //printPostOrder
  cout << "print post-order" << endl;
  printPostOrder(root);
  cout << endl;

  //printBFS
  cout << "print BFS" << endl;
  printBFS(root);
  cout << endl;

  //isBST
  cout << "isBST" << endl;
  queue<node *> node_queue;
  cout << "isBST = " << isBST(node_queue, root) << endl;

  delete root, node_2, node_3, node_4, node_5, node_6, node_7, node_8, node_9;

  return 0;
}
